package org.raymond.iworks.study.basic.algorithm.search;

/**
 * @author raymond
 * @version V1.0
 * @Description:
 * 原理介绍:
 * 1) 插值查找算法类似于二分查找,不同的是插值查找每次从自适应mid处开始查找.
 * 2) 将折半查找中的求mid索引的公式,low表示左边索引,high表示右边索引.
 * mid=(low+high)/2=low+1/2*(high-low)
 * 改为:
 * mid=low+(key-a[low])/(a[high]-a[low] *(high-low)
 * key就是findVal
 * 3) int midIndex=low+(high-low)*(key-arr[low])/(arr[high]-arr[low]); // 插值索引
 * 对应前面的代码公式:
 * int mid=left+ (right-left)*(findVal-arr[left])/(arr[right]-arr[left])
 *
 * 依据: 拉格朗日中值定理,拉格朗日的二次差值公式
 *
 * 简单理解:公式可以理解成百分比查找,因为是顺序的所以left端是最小值,key-a[left]是目标距离left的距离,
 * a[right]-a[left]是整体距离,相除就是key在整体有序数列中大致的位置.
 *
 * 差值查找适用于均匀分布的集合
 *
 * 假设一个数组 arr={1,2,3,4,...,99,100}
 * 假如我们需要查找的值是 1
 * 使用二分查找的话, 需要多次递归,才能找到1;
 * 使用插值查找算法:
 * int mid= left+ (right-left)*(findVal-arr[left])/(arr[right]-arr[left])
 * int mid = 0+(99-0)*(1-1)/(100-1)=0+99*0/99=0
 *
 * 比如查找的值是100
 * int mid=0+(99-0)*(100-1)/(100-1)=0+99*99/99=99
 *
 * 注意事项:
 * 1)对于数据量较大,关键字分布比较均匀的查找表来说,采用插值查找,速度较快
 * 2)关键字分布不均匀的情况下,该方法不一定比折半查找要好
 */
public class InsertValueSearch {
    public static void main(String[] args) {
        int[] arr = new int[100];
        for(int i=0; i<100; i++){
            arr[i]=i+1;
        }
        //System.out.println("arr:"+ Arrays.toString(arr));
        int idx = interpolationSearch(arr, 0, arr.length-1, 79);
        System.out.println("idx:"+idx);
    }

    // 插值查找算法也要求数组是有序的
    // 如果找到,返回对应的下标,如果没有找到,则返回-1
    public static int interpolationSearch(int[] arr, int left, int right, int findVal){
        System.out.println("interpolationSearch...");
        // left>right,表示查找结束
        if(left>right
                // findVal<arr[0], 防止左越界
                || findVal<arr[0]
                // findVal>arr[arr.length-1], 防止右越界
                || findVal>arr[arr.length-1])
            return -1;
        /*
        自适应
        公式可以理解成百分比查找,因为是顺序的所以left端是最小值,key-a[left]是目标距离left的距离,
        a[right]-a[left]是整体距离,相除就是key在整体有序数列中大致的位置.
         */
        int mid =left + (right-left)*(findVal-arr[left])/(arr[right]-arr[left]);
        int midVal = arr[mid];
        // 当findVal>midVal,说明findVal在右边,应该向右递归
        if(findVal>midVal){
            return interpolationSearch(arr, mid+1, right, findVal);
        // 当findVal<midVal,说明findVal在左边,应该向左递归
        }else if(findVal<midVal){
            return interpolationSearch(arr, left, mid-1, findVal);
        }else{
            return mid;
        }
    }
}
